"""
无人机路径规划算法核心模块
实现欧拉路径生成和禁飞区避让功能
"""

import networkx as nx
import math
from typing import List, Tuple, Dict, Optional
from shapely.geometry import Polygon, LineString
from dataclasses import dataclass


@dataclass
class Node:
    """节点数据类"""
    id: str
    longitude: float
    latitude: float


@dataclass
class NoFlyZone:
    """禁飞区数据类"""
    coordinates: List[Tuple[float, float]]
    
    def to_polygon(self) -> Polygon:
        """转换为Shapely多边形"""
        return Polygon(self.coordinates)


@dataclass
class PathPlanningResult:
    """路径规划结果"""
    path: List[str]
    total_distance: float
    path_details: List[Dict]
    success: bool
    message: str = ""


def calculate_distance(lon1: float, lat1: float, lon2: float, lat2: float) -> float:
    """使用Haversine公式计算两点间距离（米）"""
    R = 6371000  # 地球半径(米)
    dlat = math.radians(lat2 - lat1)
    dlon = math.radians(lon2 - lon1)
    a = (math.sin(dlat/2)**2 + math.cos(math.radians(lat1)) * 
         math.cos(math.radians(lat2)) * math.sin(dlon/2)**2)
    return R * 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))


class PathPlanner:
    """主路径规划器"""
    
    def __init__(self):
        self.graph = nx.Graph()
        self.coords = {}
        self.original_edges = set()
        self.added_edges = set()
        
    def add_node(self, node: Node) -> None:
        """添加节点"""
        self.graph.add_node(node.id)
        self.coords[node.id] = (node.longitude, node.latitude)
        
    def add_edge(self, u: str, v: str, is_original: bool = True) -> None:
        """添加边并计算权重"""
        if u not in self.coords or v not in self.coords:
            raise ValueError(f"节点 {u} 或 {v} 不存在")
            
        # 计算边的距离作为权重
        lon1, lat1 = self.coords[u]
        lon2, lat2 = self.coords[v]
        weight = calculate_distance(lon1, lat1, lon2, lat2)
        
        self.graph.add_edge(u, v, weight=weight)
        
        # 记录边的类型
        edge_key = tuple(sorted((u, v)))
        if is_original:
            self.original_edges.add(edge_key)
        else:
            self.added_edges.add(edge_key)
        
    def get_odd_degree_nodes(self) -> List[str]:
        """获取所有奇数度节点"""
        return [node for node, degree in self.graph.degree() if degree % 2 == 1]
    
    def make_eulerian(self, start: str, end: str, max_distance: float = 700) -> List[Tuple[str, str]]:
        """将图转换为欧拉图"""
        odd_nodes = self.get_odd_degree_nodes()
        expected_odds = {start, end}
        
        # 如果已经满足欧拉路径条件
        if set(odd_nodes) == expected_odds:
            return []

        # 需要进行最小权完美匹配的节点
        match_nodes = [n for n in odd_nodes if n not in expected_odds]
        
        if len(match_nodes) % 2 != 0:
            raise ValueError("无法形成欧拉路径：剩余奇节点数为奇数")
        
        # 构建子图进行匹配
        subgraph = nx.Graph()
        for i, node1 in enumerate(match_nodes):
            for j, node2 in enumerate(match_nodes[i+1:], i+1):
                distance = calculate_distance(
                    *self.coords[node1], 
                    *self.coords[node2]
                )
                if distance <= max_distance:
                    subgraph.add_edge(node1, node2, weight=distance)
        
        # 使用NetworkX的最小权完美匹配
        matching = nx.algorithms.matching.min_weight_matching(subgraph)
        
        # 添加匹配的边
        added_edges = []
        for u, v in matching:
            self.add_edge(u, v, is_original=False)
            added_edges.append((u, v))
            
        return added_edges
    
    def find_eulerian_path(self, start: str) -> List[Tuple[str, str]]:
        """找到欧拉路径"""
        if not nx.is_eulerian(self.graph):
            # 检查是否为半欧拉图
            odd_nodes = self.get_odd_degree_nodes()
            if len(odd_nodes) != 2:
                raise ValueError("图不满足欧拉路径条件")
        
        # 使用NetworkX的欧拉路径算法
        try:
            return list(nx.eulerian_path(self.graph, source=start))
        except nx.NetworkXError as e:
            raise ValueError(f"无法找到欧拉路径: {e}")
    
    def check_path_intersections(self, path_edges: List[Tuple[str, str]], 
                                no_fly_zone: NoFlyZone) -> List[Tuple[str, str, bool]]:
        """检查路径中哪些边与禁飞区相交"""
        polygon = no_fly_zone.to_polygon()
        intersections = []
        
        for u, v in path_edges:
            u_coord = self.coords[u]
            v_coord = self.coords[v]
            line = LineString([u_coord, v_coord])
            intersects = line.intersects(polygon)
            intersections.append((u, v, intersects))
            
        return intersections
    
    def find_detour_path(self, u: str, v: str, no_fly_zone: NoFlyZone) -> Optional[List[str]]:
        """为单条边找到绕飞路径"""
        polygon = no_fly_zone.to_polygon()
        u_coord = self.coords[u]
        v_coord = self.coords[v]
        
        # 尝试沿禁飞区边界绕飞
        best_route = None
        min_distance = float('inf')
        
        exterior_coords = list(polygon.exterior.coords[:-1])  # 去掉重复的最后一个点
        
        for i in range(len(exterior_coords)):
            for j in range(i+1, len(exterior_coords)):
                waypoint1 = exterior_coords[i]
                waypoint2 = exterior_coords[j]
                
                # 检查三段路径是否都不与禁飞区相交
                seg1 = LineString([u_coord, waypoint1])
                seg2 = LineString([waypoint1, waypoint2])
                seg3 = LineString([waypoint2, v_coord])
                
                if (not seg1.intersects(polygon) and 
                    not seg2.intersects(polygon) and 
                    not seg3.intersects(polygon)):
                    
                    # 计算总距离
                    d1 = calculate_distance(*u_coord, *waypoint1)
                    d2 = calculate_distance(*waypoint1, *waypoint2)
                    d3 = calculate_distance(*waypoint2, *v_coord)
                    total_distance = d1 + d2 + d3
                    
                    if total_distance < min_distance:
                        min_distance = total_distance
                        waypoint_id1 = f"W1_{i}_{j}"
                        waypoint_id2 = f"W2_{i}_{j}"
                        best_route = [u, waypoint_id1, waypoint_id2, v]
                        
                        # 添加中间节点到图中
                        if waypoint_id1 not in self.coords:
                            node1 = Node(waypoint_id1, waypoint1[0], waypoint1[1])
                            node2 = Node(waypoint_id2, waypoint2[0], waypoint2[1])
                            self.add_node(node1)
                            self.add_node(node2)
        
        return best_route
    
    def plan_path(self, 
                  nodes: List[Node],
                  edges: List[Tuple[str, str]], 
                  start: str, 
                  end: str,
                  no_fly_zones: Optional[List[NoFlyZone]] = None,
                  max_match_distance: float = 700) -> PathPlanningResult:
        """执行完整的路径规划"""
        
        # 1. 构建图
        for node in nodes:
            self.add_node(node)
            
        for u, v in edges:
            self.add_edge(u, v, is_original=True)
        
        # 2. 转换为欧拉图
        added_edges = self.make_eulerian(start, end, max_match_distance)
        
        # 3. 生成初始欧拉路径
        path_edges = self.find_eulerian_path(start)
        
        # 4. 处理禁飞区
        replacement_info = {}
        if no_fly_zones:
            for no_fly_zone in no_fly_zones:
                intersections = self.check_path_intersections(path_edges, no_fly_zone)
                
                # 处理所有相交的边
                for u, v, intersects in intersections:
                    if intersects:
                        detour = self.find_detour_path(u, v, no_fly_zone)
                        if detour:
                            replacement_info[(u, v)] = detour
                            # 添加绕飞边到图中
                            for i in range(len(detour) - 1):
                                if not self.graph.has_edge(detour[i], detour[i+1]):
                                    self.add_edge(detour[i], detour[i+1], is_original=False)
        
        # 5. 重构最终路径
        final_path = []
        for i, (u, v) in enumerate(path_edges):
            if i == 0:
                final_path.append(u)
                
            if (u, v) in replacement_info:
                replacement = replacement_info[(u, v)]
                final_path.extend(replacement[1:])  # 跳过第一个节点避免重复
            elif (v, u) in replacement_info:
                replacement = list(reversed(replacement_info[(v, u)]))
                final_path.extend(replacement[1:])  # 跳过第一个节点避免重复
            else:
                final_path.append(v)
        
        # 6. 计算路径详情
        path_edges_final = [(final_path[i], final_path[i+1]) for i in range(len(final_path)-1)]
        total_distance = 0
        path_details = []
        
        for i, (u, v) in enumerate(path_edges_final):
            u_coord = self.coords[u]
            v_coord = self.coords[v]
            distance = calculate_distance(*u_coord, *v_coord)
            total_distance += distance
            
            # 确定边类型
            edge_key = tuple(sorted((u, v)))
            if edge_key in self.original_edges:
                edge_type = "原始边"
            elif edge_key in self.added_edges:
                edge_type = "补充边"
            else:
                edge_type = "绕飞边"

            path_details.append({
                "segment": i + 1,
                "from": u,
                "to": v,
                "distance": round(distance, 2),
                "edge_type": edge_type,
                "from_coord": u_coord,
                "to_coord": v_coord
            })
        
        return PathPlanningResult(
            path=final_path,
            total_distance=round(total_distance, 2),
            path_details=path_details,
            success=True,
            message=f"成功规划路径，总长度: {total_distance:.2f}米"
        )


def create_rectangular_no_fly_zone(center_lon: float, center_lat: float, 
                                   width: float, height: float) -> NoFlyZone:
    """创建矩形禁飞区"""
    half_width = width / 2
    half_height = height / 2
    
    coordinates = [
        (center_lon - half_width, center_lat - half_height),
        (center_lon + half_width, center_lat - half_height),
        (center_lon + half_width, center_lat + half_height),
        (center_lon - half_width, center_lat + half_height)
    ]
    
    return NoFlyZone(coordinates=coordinates)
